/*
 * GraphSPT.java
 *
 * Created on 4 de enero de 2007, 10:51 AM
 */

package shortestPath;

/**
 *
 * @author tavobula
 */
public class GraphSPT {
    
    private double wt[];
    private Edge[] spt;
    
    
    /** Creates a new instance of GraphSPT */
    public GraphSPT(Graph G, int s) {
        int V=G.V();
        wt = new double[V];
        spt= new Edge[V];
        for(int v=0; v<V;++v) wt[v]=145*V;
        doublePQi pQ=new doublePQi(V,wt);
        for(int v=0; v<V; v++)pQ.insert(v);
        wt[s]=0.0;
        pQ.lower(s);
        while(!pQ.empty()){
            int v=pQ.getmin();
            if(v!=s && spt[v]==null) return;
            AdjList A = G.getAdjList(v);
            for(Edge e=A.beg();!A.end();e=A.nxt()){
                int w=e.other(v);
                double P=wt[v]+e.getWt();
                if(P<wt[w]){
                    wt[w]=P;
                    pQ.lower(w);
                    spt[w]=e;
                }
            }
        }
    }
         
        Edge pathR(int v){
            return spt[v];
        }
        
        double dist(int v){
            return wt[v];
        }
    
    
}
